1. Field of the Invention
The present invention relates to the processing of signals in communications systems, in image processing systems and to the processing of signals gathered by various types of sensors such as radar, sonar and other sensor arrays. More particularly, the present invention relates to the equalization and filtering of a signal that has been corrupted by distortion, noise and interference during transmission or otherwise. Implementations of the invention include multistage, adaptive Wiener filters that are computationally efficient.
2. Description of the Related Art
Various applications of the Wiener filter have been proposed. For example, Wiener filters have been used to recover distorted data in the field of image processing. Wiener filters have been applied to communications including, for example, to recover data from a direct sequence code division multiple access (DS-CDMA) transceiver. For many applications, the Wiener filter is the optimal linear filter that minimizes the mean-square error between a desired or transmitted signal and the filter's estimate of that signal. On the other hand, determining the coefficients of the Wiener filter can be computationally burdensome, which reduces the opportunities to use the Wiener filter in many applications in which it could otherwise provide desirable performance.
Conventional applications of Wiener filters input an N-dimensional observed data vector into an N-dimensional vector Wiener filter to extract the desired scalar signal. The generation of an N-dimensional Wiener filter is computationally intensive, with the magnitude of computations needed to calculate and later update the filter coefficients scaling as a power of the dimension N. Consequently, it is desirable to use a reduced rank Wiener filter, one having a dimension less than N, without losing significant accuracy, to process the N-dimensional observed data vector and estimate the scalar transmitted or desired signal. This reduces the complexity of the computations for determining the Wiener filter characteristics. The article, J. S. Goldstein, I. S. Reed and L. L. Scharf, “A Multistage Representation of the Wiener filter Based on Orthogonal Projections,” IEEE Transactions on Information Theory, Vol. 44, No. 7, November 1998, presents a multistage representation of the Wiener filter (MWF) based on orthogonal projections that can be generated with reduced complexity computations.
According to the Goldstein, et al., paper's strategy, orthogonal projections reduce the rank or dimensionality of the observed data to be input to the Wiener filter (i.e., the projections compress the observed data vector). The projected, reduced dimension observed data vector is then processed in a corresponding, reduced dimension Wiener filter in a manner that makes the filter more computationally efficient and facilitates the accurate estimation of the actual or transmitted data. The Wiener filter architecture is decomposed into multiple stages, so that the resulting Wiener filter is a nested set of scalar Wiener filters that process data and provide the resulting projected data to a final, reduced rank vector Wiener filter. The multistage Wiener filter architecture is well suited to the orthogonal projection of the observed data and facilitates the consequent use of a reduced rank Wiener filter.
Efforts have been made to improve on the multistage Wiener filter described in the paper by Goldstein, et al. An improvement on the Goldstein, et al., multistage Wiener filter is the adaptive filter described in M. L. Honig and J. S. Goldstein, “Adaptive Reduced-Rank Residual Correlation Algorithms for DS-CDMA Interference Suppression,” Proc. 32th Asilomar Conference Signals, Systems and Computers, Pacific Grove, Calif., November 1998. The paper by Honig, et al., discusses an adaptive version of the multistage Wiener filter known as the ResCor filter due to the filter's use of residual correlations. Here, residual correlation refers to the use of correlation data from processing previous data sets. The ResCor technique facilitates processing because it allows an earlier derived data set to be used in estimating the filter coefficients and hence reduces the requirement that updates to the filter coefficients be calculated at the same time as the filter is processing received symbols. The Honig, et al., paper provides a useful background to the detailed discussion below and so a relevant portion of the article is summarized here.
As with the multiple stage Wiener filter described in the Goldstein, et al., paper, the ResCor filter described by the Honig, et al., paper uses a series of orthogonal projections to reduce the dimensionality of the observed data vectors prior to providing the projected data vectors to the filter. Implementations of the ResCor filter utilize a projection onto a subspace that maximizes the cross-correlation between the “desired-signal” b1(i) and the “observed-signal” y(i) within the Wiener filter. The resulting ResCor filter is optimal both in terms of minimum mean-square error (MMSE) for a given rank when the covariance matrix is unknown and in terms of subspace tracking in non-stationary environments.
The ResCor strategy can be applied to generate the N×D operator SDH that projects a received (N-dimensional) data vector onto the reduced rank (D-dimensional) subspace appropriate to the reduced rank (D-dimensional) Wiener filter. Given a block of M received vectors y(i) and M training (or estimated) symbols b1(i),Y=[y(1), y(2), . . . , y(M)]  (1) b=[b1(1), . . . , b1(M)],  (2)the minimum mean square error (MMSE) filter coefficients can be estimated by simply replacing statistical averages with time or sample averages. Performing this substitution for the ResCor filter “tri-diagonalizes” the (N+1)×(N+1) extended covariance matrix
                                          R            _                    ⋀                =                              YY            _                    H                                    (        3        )                                          Y          _                =                              [                                          b                _                            Y                        ]                    .                                    (        4        )            Here and elsewhere in this discussion, the superscript H is used to designate the Hermitian transpose or complex conjugate transpose operation. When D=N, the resulting filter coefficients exactly minimize the least squares (LS) cost function
            ∑              i        =        1            M        ⁢                  ⁢                                    e          ⁡                      (            ⅈ            )                                      2        where            e      ⁡              (        ⅈ        )              =                                        b            ^                    1                ⁡                  (          ⅈ          )                    -                        b          1                ⁡                  (          ⅈ          )                      and                              b          ^                1            ⁡              (        ⅈ        )              =          z      ⁡              (        ⅈ        )            For D<N, however, the performance of this filtering strategy can differ substantially from that of the conventional least squares generated filter. That is, the filter requires intensive calculations and the accuracy of the filter, as measured by resulting signal to noise ratio, is generally worse when other than the optimal rank filter is selected.
The coefficients for the Wiener filter may be derived for the ResCor filter by using a training-based block strategy where the coefficients are determined by:
Initialization:do= b, Yo=Y  (5)For n=1, . . . , D (forward recursion):pnYn-1dH  (6)δn=∥pn∥  (7)hn=pn/δn  (8)dn=hnHYn-1  (9)Bn=null(hn)  (10)Yn=BnHYn-1  (11)Decrement n=D, . . . , 1 (backward recursion):ωn=(ωndn-1H)/∥ωn∥2=δn/∥εn∥2  (12)εn-1=dn-1−ω*nεn  (13)where εD=dD.
In the above discussion, the null(h) operator produces a matrix that can project a vector into the null space defined by the vector h. The blocking matrix operator Bn is used to block the contributions of portions of the data vector to facilitate the decomposition of the Wiener filter. The choice of blocking matrices Bn, n=1, . . . , D, does not affect the minimum mean-square error (MMSE), although the choice of blocking matrix can affect performance for a specific data record. The estimate of the block of transmitted symbols is
            b      _        ⋀    =                    ω        ⇀            1      *        ⁢                            ɛ          ->                1            .      
The adaptive Wiener filter can be used in a wide variety of applications with a variety of levels of assumptions on the nature of the signals. If all signals are known, as would be the case when a training sequence is provided to the filter, then the filter can be implemented as detailed above. Similarly, if known pilot symbols are transmitted with data, the filter can be updated employing the pilot symbols as they occur. Often in practice the Wiener filter is not provided an explicit training signal. This can be overcome in many smoothing problems or in many communications problems by utilizing, for b, a signal that corresponds to the received data after data decisions have been made on the filter output in the well-known decision-directed mode of adaptation. Another blind version of the preceding strategy for deriving the filter coefficients for CDMA communications can be obtained simply by substituting s1 (the spreading code for the desired user) for p1 in the preceding coefficient generation discussion. In addition, in an array processing environment prior knowledge of the direction of the desired signal could be captured with a steering vector, s1, and this steering vector could also be used for p1 in coefficient generation. In both of these preceding cases this would imply that the first stage of the filter is not adaptive but that the remainder of the algorithm proceeds as detailed above. It should be noted that, for these versions incorporating a non-adaptive first stage, the resulting set of forward recursions does not exactly tri-diagonalize the extended sample covariance matrix. Consequently, these versions may not perform as well as a training-based version with all stages adaptive.
The computations required to determine the coefficients of the Wiener filter in the preceding discussion for small D are modest in comparison with reduced-rank techniques that require the computation of eigenvectors or inversion of the sample covariance matrix R−YYH.Nevertheless, determining the coefficients for the Wiener filter of the Honig, et al., paper is relatively expensive as compared to less effective but also less expensive filters and equalizers currently employed in many applications.
The adaptive multistage Wiener filter described in equations above is generally illustrated in FIG. 1, which is the implementation of a conventional multistage Wiener filter shown in FIG. 2 of the article, D. C. Ricks and J. S. Goldstein, “Efficient Architectures for Implementing Adaptive Algorithms”, Proceedings of the 2000 Antenna Applications Symposium, Allerton Park, Monticello, Ill. Sep. 20-22, 2000. The Ricks, et al., implementation is essentially the multistage Wiener filter of Honig, et al., discussed above. It should be noted in FIG. 1 the linear filter blocks represent the vector operationsdi=hiH{right arrow over (y)}i-1.
A linear filter component of a multistage Wiener filter is illustrated in FIG. 1(a) and includes a set of linear filter elements h1 and h2 along a forward recursion path within the linear filter. The first filter element h1 may, for example, be a matched filter that represents a zero order or a priori channel characterization. This first filtering is equivalent to projecting the input data vectors onto a steering vector {right arrow over (s)}. This was the implementation proposed by Ricks, et al. In the Ricks, et al., configuration, the d output by the h1 filter element (labeled {right arrow over (s)} in their article) is the first projection of the input data vector along the direction of the filter's steering vector. That first d estimate is projected back to the original data vector by the h1′ filter element and that estimate is subtracted from the data vector {right arrow over (y)}0 to provide the vector {right arrow over (y)}1. The vector {right arrow over (y)}1 is a first estimate of the interference in the received data vector. As with other multistage Wiener filters, the Ricks, et al., multistage Wiener filter focuses on the most significant portion of the interference and provides successive estimates of the successively less important interference sources in additional stages of the filter.
Thus, the next filter element h2 is used to estimate the first interference source. The resulting output of the h2 filter element is then projected back onto the data vector direction and the first interference estimate is subtracted from the vector {right arrow over (y)}1 to produce a new vector {right arrow over (y)}2 that should be dominated by a second interference source. Successive stages function in a similar way to that described for the h2 filter element. In the linear filter illustrated in FIG. 1(a), the succession of stages is truncated after a desired number of stages that might, for example, represent a computationally desirable approximation of the Wiener filter. This truncation is illustrated in FIG. 1(a) by the terminator.
The backward recursion illustrated in FIG. 1(a) and described in equations 12 and 13 above is then performed to generate the scalar filter outputz=ω*1ε1.that represents the estimate of the signal corresponding to the current transmitted symbol, with the various interference estimates subtracted along the backward recursion path according to the equivalent weight vector {right arrow over (ω)} illustrated by the collected gain elements shown in FIG. 1(a). FIG. 1(b) shows the calculations used to adapt the filter coefficients h and the filter weights. The element indicated by ∥(.)∥ in FIG. 1(b) represents the calculation of a vector magnitude. These calculations are performed at the symbol rate over, for example, a block to generate an update to the filter coefficients and the filter weights at the update rate.
From the FIG. 1 illustration and the equations and discussion above of the Honig, et al., filter, the computational complexity can be determined for D filter stages, data vector lengths of N, and data blocks of size M. Here, the computational complexity is given as the total number of scalar arithmetic operations to update the filter and is given by: 10DNM+5DM+5NM. For example, where D=10, N=100 and M=1000, the complexity of the FIG. 1 filter is 1.055*107. It would be desirable to achieve the performance of the multistage adaptive Wiener filter at a reduced computational cost.